24.9 KB · ⇊ 15 parts · ⤓ Micron 24.9 KB · ⤓ HTML 191.0 KB

top

Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:

N = a 2 − − b 2 . {\displaystyle N=a^{2}-b^{2}.}

That difference is algebraically factorable as ( a + b ) ( a − − b ) {\displaystyle (a+b)(a-b)} ; if neither factor equals one, it is a proper factorization of N.

Each odd number has such a representation. Indeed, if N = c d {\displaystyle N=cd} is a factorization of N, then

N = ( c + d 2 ) 2 − − ( c − − d 2 ) 2 . {\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}.}

Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)

In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either by itself.

• Basic method

• Fermat's and trial division

• Sieve improvement

• Optimal a m a x {\displaystyle a_{\mathrm {max} }}

• Premise

• Finding the Optimum

• Cost

• Facts

• Example

• Multiplier improvement

• Other improvements

• See also

• Notes

• References

• External links

One tries various values of a, hoping that a 2 − − N = b 2 {\displaystyle a^{2}-N=b^{2}} , a square.

For example, to factor N = 5959 {\displaystyle N=5959} , the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then b 2 = 78 2 − − 5959 = 125 {\displaystyle b^{2}=78^{2}-5959=125} . Since 125 is not a square, a second try is made by increasing the value of a by 1. The second attempt also fails, because 282 is again not a square.

| Try: | 1 | 2 | 3 |

|---|---|---|---|

| a | 78 | 79 | 80 |

| b 2 | 125 | 282 | 441 |

| b | 11.18 | 16.79 | 21 |

The third try produces the perfect square of 441. Thus, a = 80 {\displaystyle a=80} , b = 21 {\displaystyle b=21} , and the factors of 5959 are a − − b = 59 {\displaystyle a-b=59} and a + b = 101 {\displaystyle a+b=101} .

Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is, a + b {\displaystyle a+b} is the smallest factor ≥ the square-root of N, and so a − − b = N / ( a + b ) {\displaystyle a-b=N/(a+b)} is the largest factor ≤ root-N. If the procedure finds N = 1 ⋅ ⋅ N {\displaystyle N=1\cdot N} , that shows that N is prime.

For N = c d {\displaystyle N=cd} , let c be the largest subroot factor. a = ( c + d ) / 2 {\displaystyle a=(c+d)/2} , so the number of steps is approximately ( c + d ) / 2 − − N = ( d − − c ) 2 / 2 = ( N − − c ) 2 / 2 c {\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c} .

If N is prime (so that c = 1 {\displaystyle c=1} ), one needs O ( N ) {\displaystyle O(N)} steps. This is a bad way to prove primality. But if N has a factor close to its square root, the method works quickly. More precisely, if c differs less than ( 4 N ) 1 / 4 {\displaystyle {\left(4N\right)}^{1/4}} from N {\displaystyle {\sqrt {N}}} , the method requires only one step; this is independent of the size of N.

Consider trying to factor the prime number N = 2,345,678,917, but also compute b and a − b throughout. Going up from N {\displaystyle {\sqrt {N}}} rounded up to the next integer, which is 48,433, we can tabulate:

| Try | 1st | 2nd | 3rd | 4th |

|---|---|---|---|---|

| a | 48,433 | 48,434 | 48,435 | 48,436 |

| b 2 | 76,572 | 173,439 | 270,308 | 367,179 |

| b | 276.7 | 416.5 | 519.9 | 605.9 |

| a − b | 48,156.3 | 48,017.5 | 47,915.1 | 47,830.1 |

In practice, one wouldn't bother with that last row until b is an integer. But observe that if N had a subroot factor above a − − b = 47830.1 {\displaystyle a-b=47830.1} , Fermat's method would have found it already.

Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.

This all suggests a combined factoring method. Choose some bound a m a x > N {\displaystyle a_{\mathrm {max} }>{\sqrt {N}}} ; use Fermat's method for factors between N {\displaystyle {\sqrt {N}}} and a m a x {\displaystyle a_{\mathrm {max} }} . This gives a bound for trial division which is a m a x − − a m a x 2 − − N {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}} . In the above example, with a m a x = 48436 {\displaystyle a_{\mathrm {max} }=48436} the bound for trial division is 47830. A reasonable choice could be a m a x = 55000 {\displaystyle a_{\mathrm {max} }=55000} giving a bound of 28937.

In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:

| a | 60,001 | 60,002 |

|---|---|---|

| b 2 | 1,254,441,084 | 1,254,561,087 |

| b | 35,418.1 | 35,419.8 |

| a − b | 24,582.9 | 24,582.2 |

When considering the table for N = 2345678917 {\displaystyle N=2345678917} , one can quickly tell that none of the values of b 2 {\displaystyle b^{2}} are squares:

| a | 48,433 | 48,434 | 48,435 | 48,436 |

|---|---|---|---|---|

| b 2 | 76,572 | 173,439 | 270,308 | 367,179 |

| b | 276.7 | 416.5 | 519.9 | 605.9 |

It is not necessary to compute all the square-roots of a 2 − − N {\displaystyle a^{2}-N} , nor even examine all the values for a. Squares are always congruent to 0, 1, 4, 5, 9, 16 modulo 20. The values repeat with each increase of a by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), a 2 − − N {\displaystyle a^{2}-N} produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, a 2 {\displaystyle a^{2}} must be 1 mod 20, which means that a is 1, 9, 11 or 19 mod 20; it will produce a b 2 {\displaystyle b^{2}} which ends in 4 mod 20 and, if square, b will end in 2 or 8 mod 10.

This can be performed with any modulus. Using the same N = 2345678917 {\displaystyle N=2345678917} ,

One generally chooses a power of a different prime for each modulus.

Given a sequence of a-values (start, end, and step) and a modulus, one can proceed thus:

But the recursion is stopped when few a-values remain; that is, when (aend-astart)/astep is small. Also, because a's step-size is constant, one can compute successive b2's with additions.

An optimal a m a x {\displaystyle a_{\mathrm {max} }} can be computed using derivative methods.

The cost of executing Fermat’s method from N {\displaystyle {\sqrt {N}}} up to a m a x {\displaystyle a_{\mathrm {max} }} is roughly proportional to a constant we will call d {\displaystyle d} . Using sieving we can reduce it by some constant we call l {\displaystyle l} . In the combined method the trial division bound becomes a m a x − − a m a x 2 − − N {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}} . Writing a m a x = N + d {\displaystyle a_{\mathrm {max} }={\sqrt {N}}+d} , one gets:

a m a x 2 − − N = ( N + d ) 2 − − N = N 2 + 2 N d + d 2 − − N = 2 N d + d 2 {\displaystyle a_{\mathrm {max} }^{2}-N=({\sqrt {N}}+d)^{2}-N={\sqrt {N}}^{2}+2{\sqrt {N}}d+d^{2}-N=2{\sqrt {N}}d+d^{2}}

Substitute the new formula, we get

a m a x − − a m a x 2 − − N → → a m a x − − 2 N d + d 2 {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}\to a_{\mathrm {max} }-{\sqrt {2{\sqrt {N}}d+d^{2}}}}

The goal is to choose a a m a x {\displaystyle a_{\mathrm {max} }} such that C ( d , N , l ) = d l + ( a m a x − − 2 N d + d 2 ) → → d 1 l + ( N + d ) − − 2 N d + d 2 = N + d ( 1 + 1 l ) − − 2 N d + d 2 {\displaystyle C\left(d,N,l\right)={\frac {d}{l}}+\left(a_{\mathrm {max} }-{\sqrt {2{\sqrt {N}}d+d^{2}}}\right)\to d{\frac {1}{l}}+\left({\sqrt {N}}+d\right)-{\sqrt {2{\sqrt {N}}d+d^{2}}}={\sqrt {N}}+d\left(1+{\frac {1}{l}}\right)-{\sqrt {2{\sqrt {N}}d+d^{2}}}} is minimized.

Differentiate C ( d , N , l ) {\displaystyle C\left(d,N,l\right)} with respect to d {\displaystyle d} . Due to the linearity of derivatives

d d d N + d ( 1 + 1 l ) − − 2 N d + d 2 = d d d N + d d d d ( 1 + 1 l ) − − d d d 2 N d + d 2 {\displaystyle {\frac {d}{dd}}{\sqrt {N}}+d\left(1+{\frac {1}{l}}\right)-{\sqrt {2{\sqrt {N}}d+d^{2}}}={\frac {d}{dd}}{\sqrt {N}}+{\frac {d}{dd}}d\left(1+{\frac {1}{l}}\right)-{\frac {d}{dd}}{\sqrt {2{\sqrt {N}}d+d^{2}}}}

Because N {\displaystyle {\sqrt {N}}} doesn't depend on d {\displaystyle d} we can drop that derivative term

for the d ( 1 + 1 l ) {\displaystyle d\left(1+{\frac {1}{l}}\right)} term, use the multiple rule ( f g ) ′ = f ′ g + g ′ f {\displaystyle \left(fg\right)'=f'g+g'f} :

( d ( 1 + 1 l ) ) ′ = d ′ ( 1 + 1 l ) + ( 1 + 1 l ) ′ d = ( 1 + 1 l ) {\displaystyle \left(d\left(1+{\frac {1}{l}}\right)\right)'=d'\left(1+{\frac {1}{l}}\right)+\left(1+{\frac {1}{l}}\right)'d=\left(1+{\frac {1}{l}}\right)}

For the last term, we use the chain rule ( f ( g ) ) ′ = f ′ ( g ) g ′ {\displaystyle \left(f\left(g\right)\right)'=f'\left(g\right)g'} and the power rule x n = n x n − − 1 {\displaystyle x^{n}=nx^{n-1}}

d d d 2 N d + d 2 = ( 2 N d + d 2 ) − − 1 2 2 d d d 2 N d + d 2 = ( 2 N d + d 2 ) − − 1 2 2 ( 2 N + 2 d ) = ( 2 N d + d 2 ) − − 1 2 ( N + d ) {\displaystyle {\frac {d}{dd}}{\sqrt {2{\sqrt {N}}d+d^{2}}}={\frac {\left(2{\sqrt {N}}d+d^{2}\right)^{-{\frac {1}{2}}}}{2}}{\frac {d}{dd}}2{\sqrt {N}}d+d^{2}={\frac {\left(2{\sqrt {N}}d+d^{2}\right)^{-{\frac {1}{2}}}}{2}}\left(2{\sqrt {N}}+2d\right)=\left(2{\sqrt {N}}d+d^{2}\right)^{-{\frac {1}{2}}}\left({\sqrt {N}}+d\right)} Substitute the known derivate formulas

d d d N + d d d d ( 1 + 1 l ) − − d d d 2 N d + d 2 = ( 1 + 1 l ) − − ( 2 N d + d 2 ) − − 1 2 ( N + d ) {\displaystyle {\frac {d}{dd}}{\sqrt {N}}+{\frac {d}{dd}}d\left(1+{\frac {1}{l}}\right)-{\frac {d}{dd}}{\sqrt {2{\sqrt {N}}d+d^{2}}}=\left(1+{\frac {1}{l}}\right)-\left(2{\sqrt {N}}d+d^{2}\right)^{-{\frac {1}{2}}}\left({\sqrt {N}}+d\right)}

To find the minimum, notice at the minimum the derivative vanishes, so st the derivative to 0

( 2 N d + d 2 ) − − 1 2 ( N + d ) = 0 → → N + d 2 N d + d 2 = 1 + 1 l {\displaystyle \left(2{\sqrt {N}}d+d^{2}\right)^{-{\frac {1}{2}}}\left({\sqrt {N}}+d\right)=0\to {\frac {{\sqrt {N}}+d}{\sqrt {2{\sqrt {N}}d+d^{2}}}}=1+{\frac {1}{l}}}

Square both sides to remove the root then cross multiply

( N + d 2 N d + d 2 ) 2 = ( 1 + 1 l ) 2 → → ( N + d ) 2 2 N d + d 2 = ( 1 + 1 l ) 2 → → ( N + d ) 2 = ( 2 N d + d 2 ) ( 1 + 1 l ) 2 {\displaystyle \left({\frac {{\sqrt {N}}+d}{\sqrt {2{\sqrt {N}}d+d^{2}}}}\right)^{2}=\left(1+{\frac {1}{l}}\right)^{2}\to {\frac {\left({\sqrt {N}}+d\right)^{2}}{2{\sqrt {N}}d+d^{2}}}=\left(1+{\frac {1}{l}}\right)^{2}\to \left({\sqrt {N}}+d\right)^{2}=\left(2{\sqrt {N}}d+d^{2}\right)\left(1+{\frac {1}{l}}\right)^{2}}

Expand LHS

( N + d ) 2 = ( 2 N d + d 2 ) ( 1 + 1 l ) 2 → → N + 2 N d + d 2 = ( 2 N d + d 2 ) ( 1 + 1 l ) 2 {\displaystyle \left({\sqrt {N}}+d\right)^{2}=\left(2{\sqrt {N}}d+d^{2}\right)\left(1+{\frac {1}{l}}\right)^{2}\to N+2{\sqrt {N}}d+d^{2}=\left(2{\sqrt {N}}d+d^{2}\right)\left(1+{\frac {1}{l}}\right)^{2}}

Bring the right side to the left, Factor the common factor, Then, bring the second term to the right-hand side

N + 2 N d + d 2 = ( 2 N d + d 2 ) ( 1 + 1 l ) 2 → → N = ( 2 N d + d 2 ) [ ( 1 + 1 l ) 2 − − 1 ] {\displaystyle N+2{\sqrt {N}}d+d^{2}=\left(2{\sqrt {N}}d+d^{2}\right)\left(1+{\frac {1}{l}}\right)^{2}\to N=\left(2{\sqrt {N}}d+d^{2}\right)\left[\left(1+{\frac {1}{l}}\right)^{2}-1\right]}

Simplify the bracket

( 1 + 1 l ) 2 − − 1 = 1 2 + 2 × × 1 × × 1 l + ( 1 l ) 2 − − 1 = 2 l + 1 l 2 = 2 l + 1 l 2 {\displaystyle \left(1+{\frac {1}{l}}\right)^{2}-1=1^{2}+2\times 1\times {\frac {1}{l}}+\left({\frac {1}{l}}\right)^{2}-1={\frac {2}{l}}+{\frac {1}{l^{2}}}={\frac {2l+1}{l^{2}}}}

So, the equation is now

N = ( 2 N d + d 2 ) 2 l + 1 l 2 → → N l 2 = ( 2 N d + d 2 ) ( 2 l + 1 ) {\displaystyle N=\left(2{\sqrt {N}}d+d^{2}\right){\frac {2l+1}{l^{2}}}\to Nl^{2}=\left(2{\sqrt {N}}d+d^{2}\right)\left(2l+1\right)}

To apply the quadratic formula to solve d {\displaystyle d} we have to rewrite the equation to a quadratic. Write the right side as:

( 2 N d + d 2 ) ( 2 l + 1 ) → → ( 2 l + 1 ) 2 N d + ( 2 l + 1 ) d 2 {\displaystyle \left(2{\sqrt {N}}d+d^{2}\right)\left(2l+1\right)\to \left(2l+1\right)2{\sqrt {N}}d+\left(2l+1\right)d^{2}}

Since 2 l + 1 ≠ ≠ 0 {\displaystyle 2l+1\neq 0} , you could divide through by it to get

d 2 + 2 N d − − N l 2 2 l + 1 = 0 {\displaystyle d^{2}+2{\sqrt {N}}d-{\frac {Nl^{2}}{2l+1}}=0}

This is the quadratic equation we been looking for, we can now apply the quardratic formula:

d = − − 2 N ± ± ( 2 N ) 2 − − 4 × × 1 × × ( − − N l 2 2 l + 1 ) 2 → → − − N ± ± N l + 1 2 l + 1 {\displaystyle d={\frac {-2{\sqrt {N}}\pm {\sqrt {\left(2{\sqrt {N}}\right)^{2}-4\times 1\times \left(-{\frac {Nl^{2}}{2l+1}}\right)}}}{2}}\to -{\sqrt {N}}\pm {\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}}

Since d > 0 {\displaystyle d>0} we take the positive solution. Since a m a x = N + d {\displaystyle a_{\mathrm {max} }={\sqrt {N}}+d} one gets:

a m a x = N + d → → N + − − N + N l + 1 2 l + 1 = N l + 1 2 l + 1 {\displaystyle a_{\mathrm {max} }={\sqrt {N}}+d\to {\sqrt {N}}+-{\sqrt {N}}+{\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}={\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}}

Substitute our optimal d {\displaystyle d} into C ( d , N , l ) {\displaystyle C\left(d,N,l\right)}

N + d ( 1 + 1 l ) − − 2 N d + d 2 → → N + ( − − N + N l + 1 2 l + 1 ) ( 1 + 1 l ) − − 2 N ( − − N + N l + 1 2 l + 1 ) + ( − − N + N l + 1 2 l + 1 ) 2 {\displaystyle {\sqrt {N}}+d\left(1+{\frac {1}{l}}\right)-{\sqrt {2{\sqrt {N}}d+d^{2}}}\to {\sqrt {N}}+\left(-{\sqrt {N}}+{\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}\right)\left(1+{\frac {1}{l}}\right)-{\sqrt {2{\sqrt {N}}\left(-{\sqrt {N}}+{\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}\right)+\left(-{\sqrt {N}}+{\sqrt {N}}{\frac {l+1}{\sqrt {2l+1}}}\right)^{2}}}}

Simplifying the monster of an equation, we get N ( 2 l + 1 − − 1 ) l {\displaystyle {\frac {{\sqrt {N}}\left({\sqrt {2l+1}}-1\right)}{l}}} .

• If l = 1 {\displaystyle l=1} that means no sieving, a m a x = 2 N 3 {\displaystyle a_{\mathrm {max} }={\frac {2{\sqrt {N}}}{3}}} and the cost becomes N ( 3 − − 1 ) {\displaystyle {\sqrt {N}}\left({\sqrt {3}}-1\right)} , which is still better than pure trial division or pure Fermat

• The a m a x − − a m a x 2 − − N {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}} which is the trial division bound becomes N 2 l + 1 {\displaystyle {\frac {\sqrt {N}}{\sqrt {2l+1}}}} when subsututing the optimal.

Using the same N = 2345678917 {\displaystyle N=2345678917} , if there's no sieving then you should choose a m a x {\displaystyle a_{\mathrm {max} }} around 55924.69838392813, the reasonable choice a m a x = 55000 {\displaystyle a_{\mathrm {max} }=55000} is not that far off from the optimal with a bound of 28937, but the optimal choice gets a bound of 27962. If we are sieving modulo 20, then l = 1 4 20 = 5 {\displaystyle l={\frac {1}{\frac {4}{20}}}=5} and you should choose around 2345678917 6 11 ≈ ≈ 87617.1636423325 {\displaystyle {\sqrt {2345678917}}{\frac {6}{\sqrt {11}}}\approx 87617.1636423325} and this should intuitively make sense. If the Fermat part costs less, the spend more time in the Fermat part to lower a m a x − − a m a x 2 − − N {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}

Fermat's method works best when there is a factor near the square-root of N.

If the approximate ratio of two factors ( d / c {\displaystyle d/c} ) is known, then a rational number v / u {\displaystyle v/u} can be picked near that value. N u v = c v ⋅ ⋅ d u {\displaystyle Nuv=cv\cdot du} , and Fermat's method, applied to Nuv, will find the factors c v {\displaystyle cv} and d u {\displaystyle du} quickly. Then gcd ( N , c v ) = c {\displaystyle \gcd(N,cv)=c} and gcd ( N , d u ) = d {\displaystyle \gcd(N,du)=d} . (Unless c divides u or d divides v.)

Generally, if the ratio is not known, various u / v {\displaystyle u/v} values can be tried, and try to factor each resulting Nuv. R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in O ( N 1 / 3 ) {\displaystyle O(N^{1/3})} time.cite-ref-1[1]

The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieve and general number field sieve, the best-known algorithms for factoring large semiprimes, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of a 2 − − n {\displaystyle a^{2}-n} , it finds a subset of elements of this sequence whose product is a square, and it does this in a highly efficient manner. The end result is the same: a difference of squares mod n that, if nontrivial, can be used to factor n.

• Completing the square

• Factorization of polynomials

• Factor theorem

• FOIL rule

• Monoid factorisation

• Pascal's triangle

• Prime factor

• Factorization

• Euler's factorization method

• Integer factorization

• Program synthesis

• Table of Gaussian integer factorizations

• Unique factorization

cite-note-11. ↑ citereflehman1974Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940. JSTOR 2005940.

• citereffermat1894Fermat (1894), Oeuvres de Fermat, vol. 2, p. 256

• citerefmckee1999McKee, J (1999). "Speeding Fermat's factoring method". Mathematics of Computation. 68 (228): 1729–1737. doi:10.1090/S0025-5718-99-01133-3.

• Fermat's factorization running time, at blogspot.in

• Fermat's Factorization Online Calculator, at windowspros.ru